package com.datastructure.binarytree;

/**
 * @author: 临晖
 * @date: 2023/10/22
 * @description:
 */


import java.util.*;

/**
 * 二叉树得三种遍历方式
 * 递归
 * 迭代
 * 通用迭代
 */
public class Solution01 {

    //public List<Integer> preorderTraversal(TreeNode root) {
    //    //递归
    //    //ArrayList<Integer> list = new ArrayList<>();
    //    //preorder(root, list);
    //    //return list;
    //
    //
    //    //迭代
    //    //ArrayList<Integer> list = new ArrayList<>();
    //    //if (root == null) {
    //    //    return list;
    //    //}
    //    //Stack<TreeNode> stack = new Stack<>();
    //    //stack.push(root);
    //    //while (!stack.isEmpty()) {
    //    //    TreeNode node = stack.pop();
    //    //    list.add(node.val);
    //    //
    //    //    if (node.right !=  null) {
    //    //        stack.add(node.right);
    //    //    }
    //    //
    //    //    if (node.left != null) {
    //    //        stack.push(node.left);
    //    //    }
    //    //}
    //    //
    //    //return list;
    //
    //    //通用迭代
    //    ArrayList<Integer> list = new ArrayList<>();
    //    if (root == null) {
    //        return list;
    //    }
    //
    //    Stack<TreeNode> stack = new Stack<>();
    //    stack.push(root);
    //    while (!stack.isEmpty()) {
    //        TreeNode node = stack.peek();
    //
    //        if (node != null) {
    //            stack.pop();        //防止重复
    //
    //
    //            if (node.right != null) {
    //                stack.push(node.right);
    //            }
    //
    //            if (node.left != null) {
    //                stack.push(node.left);
    //            }
    //
    //            stack.push(node);
    //            stack.push(null);
    //
    //        } else {
    //            stack.pop();        //弹出标记
    //
    //            list.add(stack.pop().val);
    //        }
    //    }
    //
    //    return list;
    //}
    //
    //public void preorder(TreeNode root, List<Integer> result) {
    //    if (root == null) {
    //        return;
    //    }
    //
    //    //中
    //    result.add(root.val);
    //    //左
    //    preorder(root.left, result);
    //    //右
    //    preorder(root.right, result);
    //}
    //
    //
    //public List<Integer> inorderTraversal(TreeNode root) {
    //    ArrayList<Integer> list = new ArrayList<>();
    //    if (root == null) {
    //        return list;
    //    }
    //
    //    Stack<TreeNode> stack = new Stack<>();
    //    TreeNode curr = root;
    //    while (curr != null || !stack.isEmpty()) {
    //
    //        if (curr != null) {
    //            stack.push(curr);
    //            curr = curr.left;
    //        } else {
    //            curr = stack.pop();
    //            list.add(curr.val);
    //            curr = curr.right;
    //        }
    //    }
    //
    //
    //
    //    return list;
    //
    //}


    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();

        if (root == null) {
            return res;
        }

        //创建栈
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();

            if (node != null) {
                node = stack.pop();
                stack.push(node);
                stack.push(null);
                if (node.right != null) {
                    stack.push(node.right);
                }

                if (node.left != null) {
                    stack.push(node.left);
                }

            } else {
                stack.pop();        //弹出空
                node = stack.pop();
                res.add(node.val);

            }
        }

        return res;
    }







}
